package com.zj.leetcode.easy.hash;

import java.util.HashMap;
import java.util.HashSet;

/**
 * @program: algorithm
 * @description: 存在重复元素 II
 * 219 contains-duplicate-ii
 * @author: Zhang Bo
 * @create: 2022-01-14 17:05
 **/
public class ContainsDuplicateIi {
    public static void main(String[] args) {
        int[] nums = {1,0,1,1};
        int k = 1;
        Solution solution = new ContainsDuplicateIi().new Solution();
        System.out.println(solution.containsNearbyDuplicate(nums, k));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean containsNearbyDuplicate(int[] nums, int k) {

            HashMap<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                Integer put = map.put(nums[i], i);
                if (put != null) {
                    if (Math.abs(put - i) <= k) {
                        return true;
                    }
                }
            }
            return false;
        }

        /**
         * 想一下滑动窗口的实现方式，就懂了
         * @param nums
         * @param k
         * @return
         */
        public boolean containsNearbyDuplicate01(int[] nums, int k) {
            HashSet<Integer> set = new HashSet<>();
            for (int i = 0; i < nums.length; i++) {
                if(i > k){
                    set.remove(nums[i - k - 1]);
                }
                if (!set.add(nums[i])) {
                    return true;
                }
            }
            return false;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
